Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

  1. public class Solution {
  2.   public List<String> restoreIpAddresses(String s) {
  3.     List<String> res = new ArrayList<String>();
  4.     helper(s, 0, 0, "", res);
  5.     return res;
  6.   }
  8.   void helper(String s, int index, int segment, String sol, List<String> res) {
  9.     if (segment == 4 && index == s.length()) {
  10.       res.add(sol);
  11.       return;
  12.     }
  14.     // too many characters left
  15.     if (s.length() > index + (4 - segment) * 3) {
  16.       return;
  17.     }
  19.     // not enough characters left
  20.     if (s.length() < index + (4 - segment)) {
  21.       return;
  22.     }
  24.     for (int i = index; i < index + 3 && i < s.length(); i++) {
  25.       String str = s.substring(index, i + 1);
  26.       int num = Integer.parseInt(str);
  28.       if ((s.charAt(index) == '0' && i > index) || (num > 255)) {
  29.         return;
  30.       }
  32.       helper(s, i + 1, segment + 1, sol + str + (segment == 3 ? "" : "."), res);
  33.     }
  34.   }
  35. }